import java.util.*;

/**
 * @author ZJX
 * @version 1.0
 * @descption 二叉树
 * @since 2025/10/12 20:23
 */
public class Tree {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (Math.abs(left - right) > 1) {
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelRet = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                levelRet.add(poll.val);
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            ret.add(levelRet);
        }
        return ret;
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            List<Integer> level = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (flag) {
                    level.add(node.val);
                } else {
                    level.add(0, node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            flag = !flag;
            ret.add(level);
        }
        return ret;
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    ret.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return ret;
    }

    public List<Integer> rightSideViewDFS(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        dfsRight(root, 0, ret);
        return ret;
    }

    private void dfsRight(TreeNode root, int depth, List<Integer> ret) {
        if (root == null) return;
        if (depth == ret.size()) {
            ret.add(root.val);
        }
        dfsRight(root.right, depth + 1, ret);
        dfsRight(root.left, depth + 1, ret);
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            ret.add(node.val);
            cur = node.right;
        }
        return ret;
    }

    private void dfsIn(TreeNode node, List<Integer> ret) {
        if (node == null) return;
        dfsIn(node.left, ret);
        ret.add(node.val);
        dfsIn(node.right, ret);
    }


    public List<Integer> preorderTraversalDFS(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        dfsPre(root, ret);
        return ret;
    }

    private void dfsPre(TreeNode root, List<Integer> ret) {
        if (root == null) return;
        ret.add(root.val);
        dfsPre(root.left, ret);
        dfsPre(root.right, ret);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ret.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ret;
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return checkTree(root.left, root.right);
    }

    private boolean checkTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return checkTree(p.left, q.right) && checkTree(p.right, q.left);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
    }

    public List<Integer> postorderTraversalDFS(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        dfsPost(root, ret);
        return ret;
    }

    private void dfsPost(TreeNode node, List<Integer> ret) {
        if (node == null) {
            return;
        }
        dfsPost(node.left, ret);
        dfsPost(node.right, ret);
        ret.add(node.val);
    }

    public List<List<Integer>> levelOrderDFS(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        dfslevelOrderDFS(root, 0, ret);
        return ret;
    }

    private void dfslevelOrderDFS(TreeNode node, int level, List<List<Integer>> ret) {
        if (node == null) {
            return;
        }
        if (level == ret.size()) {
            ret.add(new LinkedList<>());
        }
        ret.get(level).add(node.val);
        dfslevelOrderDFS(node.left, level + 1, ret);
        dfslevelOrderDFS(node.right, level + 1, ret);
    }

    public List<List<Integer>> zigzagLevelOrderDFS(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        dfszigzagLevelOrderDFS(root, 0, ret);
        return ret;
    }

    private void dfszigzagLevelOrderDFS(TreeNode node, int level, List<List<Integer>> ret) {
        if (node == null) {
            return;
        }
        if (level == ret.size()) {
            ret.add(new LinkedList<>());
        }
        List<Integer> list = ret.get(level);
        if (level % 2 == 0) {
            list.add(node.val);
        } else {
            list.add(0, node.val);
        }
        dfszigzagLevelOrderDFS(node.left, level + 1, ret);
        dfszigzagLevelOrderDFS(node.right, level + 1, ret);
    }

    public boolean isValidBSTDFS(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 初始上下界用long类型的极值，避免int边界值冲突
        return dfsIsValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfsIsValidBST(TreeNode node, long minValue, long maxValue) {
        if (node == null) {
            return true;
        }
        int value = node.val;
        if (value <= minValue || value >= maxValue) {
            return false;
        }

        return dfsIsValidBST(node.left, minValue, value) && dfsIsValidBST(node.right, value, maxValue);
    }

    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        long preVal = Long.MIN_VALUE;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            if (node.val <= preVal) {
                return false;
            }
            preVal = node.val;
            root = node.right;
        }
        return true;
    }

    public TreeNode lowestCommonAncestorW(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (Math.abs(left - right) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    int max;

    public int diameterOfBinaryTree(TreeNode root) {
        getDepth(root);
        return max;
    }

    private int getDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = getDepth(node.left);
        int right = getDepth(node.right);
        max = Math.max(max, left + right);
        return Math.max(left, right) + 1;
    }

    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(maxGain(node.left), 0);
        int right = Math.max(maxGain(node.right), 0);
        int cur = node.val + left + right;
        maxSum = Math.max(cur, maxSum);
        return node.val + Math.max(left, right);
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        dfsBinaryTreePaths(root, new StringBuilder(), ret);
        return ret;
    }

    private void dfsBinaryTreePaths(TreeNode node, StringBuilder path, List<String> ret) {
        int len = path.length();
        path.append(node.val);

        if (node.left == null && node.right == null) {
            ret.add(path.toString());
        } else {
            path.append("->");
            if (node.left != null) {
                dfsBinaryTreePaths(node.left, path, ret);
            }
            if (node.right != null) {
                dfsBinaryTreePaths(node.right, path, ret);
            }
        }
        path.setLength(len); // 回溯
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return dfsSortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode dfsSortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfsSortedArrayToBST(nums, left, mid - 1);
        root.right = dfsSortedArrayToBST(nums, mid + 1, right);
        return root;
    }


    public TreeNode buildTreeIN(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap<Integer, Integer> map) {
        if (preStart > preEnd) {
            return null;
        }
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = map.get(rootVal);
        int leftSize = rootIndex - inStart;
        root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1, map);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd, map);

        return root;
    }


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildInPost(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, map);
    }

    private TreeNode buildInPost(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, HashMap<Integer, Integer> map) {
        if (postStart > postEnd) {
            return null;
        }
        int rootVal = postorder[postEnd];
        int rootIndex = map.get(rootVal);
        int leftSize = rootIndex - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = buildInPost(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1, map);
        root.right = buildInPost(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1, map);

        return root;
    }

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            map.put(postorder[i], i);
        }

        return buildFromPrePost(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1, map);
    }

    private TreeNode buildFromPrePost(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd, HashMap<Integer, Integer> map) {
        if (preStart > preEnd) {
            return null;
        }
        // 单个节点：直接返回（避免后续计算越界）
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }

        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int leftRootVal = preorder[preStart + 1];
        int leftRootPostIndex = map.get(leftRootVal);
        int leftSize = leftRootPostIndex - postStart + 1;

        root.left = buildFromPrePost(preorder, preStart + 1, preStart + leftSize, postorder, postStart, leftRootPostIndex, map);
        root.right = buildFromPrePost(preorder, preStart + leftSize + 1, preEnd, postorder, leftRootPostIndex + 1, postEnd - 1, map);

        return root;
    }

    public void flatten(TreeNode root) {
        // cur：当前正在处理的节点，从根节点开始遍历
        TreeNode cur = root;

        // 循环条件：当前节点不为空（遍历完整棵树后结束）
        while (cur != null) {
            // 若当前节点有左子树：需要将左子树移到右子树位置，并衔接原右子树
            if (cur.left != null) {
                // 1. 找到左子树的「最右节点」（左子树前序遍历的最后一个节点）
                // 因为前序遍历顺序是「根→左子树→右子树」，左子树的最后一个节点后必须接原右子树
                TreeNode left = cur.left; // 先记录左子树的根节点
                while (left.right != null) { // 一直向右找，直到找到左子树的最右节点
                    left = left.right;
                }

                // 2. 将当前节点的原右子树，接到左子树的最右节点的右指针上
                // 这一步保证了「左子树遍历完后，紧接着是原右子树」，符合前序顺序
                left.right = cur.right;

                // 3. 将左子树移到当前节点的右指针位置（替代原右子树）
                // 同时将左指针置为null（满足链表左指针为null的要求）
                cur.right = cur.left;
                cur.left = null;
            }

            // 4. 处理下一个节点：当前节点的右指针已指向「原左子树（已展开）或原右子树」
            // 继续向右遍历，直到所有节点处理完毕
            cur = cur.right;
        }
    }

    public void flattenDFS(TreeNode root) {
        // 终止条件：空节点无需处理
        if (root == null) {
            return;
        }

        // 1. 递归展开左子树和右子树
        flattenDFS(root.left);
        flattenDFS(root.right);

        // 2. 保存原右子树（后续要接在左子树末尾）
        TreeNode originalRight = root.right;

        // 3. 将左子树移到右子树位置，左指针置空
        root.right = root.left;
        root.left = null;

        // 4. 找到新右子树（原左子树）的最后一个节点
        TreeNode cur = root;
        while (cur.right != null) {
            cur = cur.right;
        }

        // 5. 将原右子树接在新右子树的末尾
        cur.right = originalRight;
    }

    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            k--;
            if (k == 0) {
                return node.val;
            }
            cur = node.right;
        }
        return -1;
    }

    int ret = 0;
    int count = 0;

    public int kthSmallestDFS(TreeNode root, int k) {
        kth(root, k);
        return ret;
    }

    private void kth(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        kth(root.left, k);
        count++;
        if (count == k) {
            ret = root.val;
            return;
        }
        kth(root.right, k);
    }

    public int findTargetNode(TreeNode root, int cnt) {
        int count = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            TreeNode node = stack.pop();
            count++;
            if (count == cnt) {
                return node.val;
            }
            cur = node.left;
        }
        return -1;
    }


    public int findTargetNodeDFS(TreeNode root, int cnt) {
        findDfs(root, cnt);
        return ret;
    }

    private void findDfs(TreeNode root, int cnt) {
        if (root == null) {
            return;
        }
        findDfs(root.right, cnt);
        count++;
        if (count == cnt) {
            ret = root.val;
            return;
        }
        findDfs(root.left, cnt);
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean isSame(TreeNode a, TreeNode b) {
        if (b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        if (a.val != b.val) {
            return false;
        }
        return isSame(a.left, b.left) && isSame(a.right, b.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return subRoot == null;
        }
        if (isSamesub(root, subRoot)) {
            return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSamesub(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        if (root.val != subRoot.val) {
            return false;
        }
        return isSamesub(root.left, subRoot.left) && isSamesub(root.right, subRoot.right);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }

    public TreeNode lowestCommonAncestorP(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<TreeNode, TreeNode> parent = new HashMap<>();
        parent.put(root, null);
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                stack.push(node.left);
                parent.put(node.left, node);
            }
            if (node.right != null) {
                stack.push(node.right);
                parent.put(node.right, node);
            }
        }
        Set<TreeNode> set = new HashSet<>();
        while (p != null) {
            set.add(p);
            p = parent.get(p);
        }
        while (!set.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }

    public List<Integer> inorderTraversalII(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            ret.add(node.val);
            cur = node.right;
        }
        return ret;
    }

    static class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {

        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {

        }

        private static int sum = Integer.MIN_VALUE;

        /**
         * 二叉树的最大路径和
         *
         * @param root TreeNode类
         * @return int整型
         */
        public int maxPathSum(TreeNode root) {
            maxGet(root);
            return sum;
        }

        private int maxGet(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = Math.max(maxGet(root.left), 0);
            int right = Math.max(maxGet(root.right), 0);
            int cur = root.val + left + right;
            sum = Math.max(cur, sum);
            return root.val + Math.max(left, right);
        }
    }

}

